package com.study.leetcode;

//https://leetcode-cn.com/problems/linked-list-cycle/submissions/
public class LinkedListCycle {
    public boolean hasCycle(ListNode head) {
        //使用快慢指针 如果这两个指针进入环内则会因为在环内一直循环而相遇
        ListNode slow = head;
        ListNode fast = head;
        //只要没有环则必定有一个指针或者这个指针的next为null的情况
        //这里注意边界 只要null就是一个正常的无环的链表
        while (slow != null && fast != null && slow.next != null && fast.next != null) {
            //快慢指针每次走的步伐不一样
            slow = slow.next;
            fast = fast.next.next;
            //如果相遇则有环
            if (slow == fast) {
                return true;
            }
        }
        //没有环
        return false;
    }
}
